package com.wyp168.leetcode;

/**
 * @ClassName AtMostNGivenDigitSetSolution
 * @Title TODO leetcode 902 最大为N的数字组合
 * @Description TODO 给定一个字符串数组digits 和 一个整数n， 统计根据数组digits中的元素组合出小于整数n的最大个数【数组中元素可重复选择】
 *              //TODO 注意：有时间限制
 * @Author wyp168
 * @Date 2022/10/18 20:39
 */
public class AtMostNGivenDigitSetSolution {
    public static void main(String[] args) {
        AtMostNGivenDigitSetSolution solution = new AtMostNGivenDigitSetSolution();

        String[] digits = {"1","2","3","4","6","7","8","9"};
        int n = 67688637;
        System.out.println(solution.atMostNGivenDigitSet(digits, n));
    }

//    public int atMostNGivenDigitSet(String[] digits, int n) {
//        int countMax = 0;
//        for (String digit : digits) {
//            if (Long.valueOf(digit) <= n ) {
//                countMax ++;
//                countMax = dfs(digit, digits, n, countMax);
//            } else {
//                break;
//            }
//        }
//        return countMax;
//    }
//
//    public int dfs(String num, String[] digits, int n, int countMax) {
//        for (String digit : digits) {
//            String tempNum = num + digit;
//            if (Long.valueOf(tempNum) <= n) {
//                countMax ++;
//                countMax = dfs(tempNum, digits, n, countMax);
//            } else {
////                return countMax;
//                break;
//            }
//        }
//        return countMax;
//    }



    public int atMostNGivenDigitSet(String[] digits, int n) {
        String s = Integer.toString(n);
        int m = digits.length, k = s.length();
        int[][] dp = new int[k + 1][2];
        dp[0][1] = 1;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < m; j++) {
                if (digits[j].charAt(0) == s.charAt(i - 1)) {
                    dp[i][1] = dp[i - 1][1];
                } else if (digits[j].charAt(0) < s.charAt(i - 1)) {
                    dp[i][0] += dp[i - 1][1];
                } else {
                    break;
                }
            }
            if (i > 1) {
                dp[i][0] += m + dp[i - 1][0] * m;
            }
        }
        return dp[k][0] + dp[k][1];
    }
}
